The present invention relates to low-density parity check (LDPC) codes, and more particularly, to encoders and methods for encoding digital data with LDPC matrices, where the encoders and methods can be applied to WiMAX, 802.11n, and other communication systems.
LDPC codes have become one of the hottest topics in current coding theory. First appearing around the middle of the twentieth century, LDPC codes have experienced an amazing comeback in the last few years since they are already equipped with very fast (probabilistic) encoding and decoding algorithms. Recovering the original codeword in the face of large amounts of noise was previously the most pressing issue, but new analytic and combinatorial tools make it possible to solve related design problems. As a result, LDPC codes are not only attractive from a theoretical point of view, but also suitable for practical applications.
Regarding implementation of encoding LDPC codes using a generator matrix, storing a very large matrix is required according to the related art, where LDPC codes typically require large blocks of a matrix to be effective and ready for use, so as to achieve better performance. Consequently, even though parity check matrices of LDPC codes may be sparse in some occasions, storing these matrices in a cost-effective manner without hindering the performance is still a problem for developers and researchers.
Please refer to FIG. 1. FIG. 1 illustrates a parity check matrix H of LDPC codes according to the related art, where a subscript ai, j of an element of the parity check matrix H may represent a shifting number f (which is typically a non-negative integer as known by those skilled in the related art), so this element can be referred to as Pf. Typically, each of a plurality of elements of the parity check matrix H is defined as a cyclic permutation matrix of a size L by L, with L representing a sub-block size, which is a sub-matrix size for the parity check matrix H. As shown in FIG. 2, FIG. 3, and FIG. 4, some examples of cyclic permutation matrices Pf with L=8 according to the related art are illustrated for better comprehension. Generally speaking, the cyclic permutation matrix Pf is produced by cyclically shifting columns of an identity matrix to the right by f number of places, where the cyclic permutation matrix Pf is substantially the identity matrix if the shifting number f is zero.
Regarding a larger number of the sub-matrix size L, for example, L=81, if the height and the width of the parity check matrix H are respectively 12 and 24 (i.e. m=12 and c=24), the corresponding codeword block length n may reach 1944 bits (i.e. 243 bytes) and the total storage volume required for the parity check matrix H may reach 2916 bytes. It is noted that storing different parity check matrices corresponding to various conditions (e.g. various code rates or various transmission parameters) is typically required according to the related art. Therefore, storage requirements for these parity check matrices have become an important issue.
In addition, in a parity generator according to the related art, such as that shown in FIG. 5, a size of a multiplier accumulator (MAC) is directly related to the number of bits processed each time. As a result, the overall hardware architecture according to the related art is huge and cost ineffective.